/**
 * 对于给定的整数 n, 如果n的k（k>=2）进制数的所有数位全为1，则称 k（k>=2）是 n 的一个好进制。
 * 以字符串的形式给出 n, 以字符串的形式返回 n 的最小好进制。
 **/
#include<iostream>
#include<string>
#include<math.h>
using namespace std;

/**
 * Solution 1:数学推导
 * 具体数学推导见leetcode官方题解
 **/
class Solution_1 {
public:
    string smallestGoodBase(string n) {
        long long num = stoll(n);
        // floor(x)：不大于x的最大整数
        // m < logkn，k>=2; k=2时m取得最大值
        // n的位数为 m+1
        int mMax = floor(log(num)/log(2));
        for(int m=mMax; m>=2; m--){
            // k = ⌊ n开m次根⌋
            // double pow( double x, double y ):计算x的y次幂
            int k = pow(num, 1.0/m);
            // 利用 n=k^0+k^1+k^2+……+k^m
            long mul = 1, sum = 1;
            for(int i=0; i<m; i++){
                mul *= k;
                sum += mul;
            }
            if(sum == num){
                return to_string(k);
            }
        }
        // 一直检查到 m=2都没能找到答案，那么可直接返回 m=1对应的k值：n-1
        return to_string(num - 1);
    }
};


/**
 * Solution 2:二分查找
 * 对于全为 1的数，二分找到进制 k，使得其转换后等于n
 * 1.确定全为1的字符串能达到的最长长度maxLen。
 * 2.对字符串的长度进行递减遍历，则现在已知输入数n，以及给定一个长度为len的全为1的字符串，
 *   现在只需确定进制k的下界和上界，用二分法去寻找满足该方程的进制k。
 * 3.当遍历过程中如果寻找到一个进制k满足进制转换方程，则直接输出该进制k即可。
 * 4.如果长度从maxLen遍历到len = 3都没有寻找到k，则结束循环直接输出输入数n - 1即可。
 * 
 * 因为全为1的字符串长度越长，说明进制数k越小，所以对长度递减遍历的时候，当找到一个存在满足方程的进制k时，该进制k就是最小的
 **/
class Solution {
public:
    string smallestGoodBase(string n){
        long long num = stoll(n);
        // @lenmax:全为1的字符串能达到的最大长度
        int lenmax = log(num) / log(2) + 1;
        for(int len=lenmax; len>2; len--){
            int left = 2, right = pow(num, 1.0/(len-1));
            while(left < right){
                int mid = left + (right - left) / 2;
                compute(mid, len) <= num ? left = mid + 1 : right = mid;
            }
            if(compute(left, len) == num){
                return to_string(left);
            }
        }
        // n-1是「全为1的字符串长度len = 2时满足进制转换方程的进制数」
        // n = 10，那进制k = 9的话就能将10转换为11
        return to_string(num - 1);
    }

    // 计算n=k^0+k^1+k^2+……+k^m
    long long compute(int k, int len){
        // leetcode在线编译做乘法long long也会溢出，改用unsigned long long
        unsigned long long mul = 1, sum = 1;
        for(int i=0; i<len-1; i++){
            mul *= k;
            sum += mul;
        }
        return sum;
    }
};

int main(){
    string str = "1000000000000000000";
    Solution s;
    string result = s.smallestGoodBase(str);
    cout<<result;
}